package leetcode.editor.week.week308;

import java.util.Arrays;

// 2389. 和有限的最长子序列
// https://leetcode.cn/problems/longest-subsequence-with-limited-sum/
public class Solution6160 {
    public static void main(String[] args) {
        Solution6160 solution6160 = new Solution6160();
        solution6160.answerQueries(new int[]{469781, 45635, 628818, 324948, 343772, 713803, 452081}, new int[]{816646, 929491});
    }

    // [4,5,2,1]
    //[3,10,21]
    //[2,3,4,5]
    //[1]
    //[1,2,3]
    //[6]
    //[624082]
    //[972985,564269,607119,693641,787608,46517,500857,140097]
    //[469781,45635,628818,324948,343772,713803,452081]
    //[816646,929491]
    public int[] answerQueries(int[] nums, int[] queries) {
        int[] ans = new int[queries.length];
        Arrays.sort(nums);
        for(int i = 0; i < queries.length; i++) {
            ans[i] = getLength(nums, queries[i]);
        }
        return ans;
    }

    public int getLength(int[] nums, int q) {
        if(nums[0] > q) return 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(sum > q) {
                return i;
            }
        }

        return nums.length;
    }
}
